package 我的Java学习_算法基础.day_08;

import java.util.Arrays;

/**
 * @author 挚爱之夕
 * @date 2021/8/25 - 08 - 25 - 15:12
 * @Description: 我的Java学习.day_08
 * @Version: 1.0
 */
public class _133_钢条切割 {
    public static void main(String[] args) {
        int ans = f(n);
        System.out.println(ans);
        Arrays.fill(memories,-1);
        ans = f1(n);
        System.out.println(ans);
        ans = dp();
        System.out.println(ans);
    }
    static int n = 10;      //初始钢条长度
    static int[] longs = {1,2,3,4,5,6,7,8,9,10};
    static int[] values = {1,5,8,16,10,17,17,20,24,30};
    //普通递归
    private static int f(int n){
        if(n==0) return 0;
        int answer = 0;
        for (int i = 1; i <= n; i++) {
            int value = values[i-1]+f(n-i);
            answer = Math.max(answer,value);
        }
        return answer;
    }
    //记忆型
    static int[] memories = new int[n+1];
    private static int f1(int n){
        if(n==0) return 0;
        int answer = 0;
        for (int i = 1; i <= n; i++) {
            //查询、没有则记录
            if (memories[n-i]==-1){
                memories[n-i] = f1(n-i);
            }
            int value = values[i-1]+memories[n-i];
            answer = Math.max(answer,value);
        }
        //记录
        memories[n] = answer;
        return answer;
    }
    //动态规划（递推）
    static int[] map = new int[n+1];
    private static int dp(){
        map[0] = 0;
        for (int i = 1; i <= n; i++) { //i是有多长的钢条，最短从1开始
            for(int j = 1;j<=i;j++){//j是左端切多长，右端取最大价值，是已经存在map里的
                //第一次和map【0】=0比存的是切一长度的，即每次新旧取最大
                map[i] = Math.max(values[j-1] + map[i-j],map[i] );
            }
        }
        return map[n];
    }

}
